import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class sort1 {
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for ( j = i-1; j >= 0 ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    public static void shellSort(int[] array) {   //2.希尔排序
        int gap = array.length;
        while(gap > 1) {
            shell(array,gap);
            gap = gap/2;
        }
        shell(array,1);
    }
    public static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (j = i-gap; j >= 0 ; j = j-gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    /**
     * 选择（从后面选最小的一个往前放）
     * @param array
     */
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[i]) {
                    swap(array,i,j);
                }
            }
        }
    }
    public static void swap(int[] array,int a,int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
    public static void selectSort1(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minindex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minindex]) {   //不交换值，换下标，可优化选择排序
                    minindex = j;
                }
            }
            if(array[minindex] < array[i]) {
                swap(array,minindex,i);
            }
        }
    }

    /**
     * 快排
     * @param array
     */
    public static void quickSort(int[] array) {
        int left = 0;
        int right = array.length-1;
        QuickSort(array,left,right);
    }
    public static void QuickSort(int[] array,int start,int end) {
        if(start >= end) {  //无左树
            return;
        }
        if(end-start+1 <= 1400) {
            insertSort1(array,start,end);
            return;
        }
        int midmaxIndex = find(array,start,end);  //三数取中
        swap(array,midmaxIndex,start);
        int partition = quickfun(array,start,end);
        QuickSort(array,start,partition-1);
        QuickSort(array,partition+1,end);
    }
    public static void insertSort1(int[] array,int start,int end) {
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for ( j = i-1; j >= start ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    public static int find(int[] array,int start,int end) {
        int mid = start+((end-start)>>1);
        if(array[start] > array[end]) {
            if(array[mid] > array[start]) return start;
            if(array[mid] < array[end]) return end;
            return mid;
        } else {
            if(array[mid] > array[end]) return end;
            if(array[mid] < array[start]) return start;
            return mid;
        }
    }
    public static int quickfun(int[] array,int start,int end){   //
        int tmp = array[start];
        int i = start;
        while(start < end) {
            while (start < end && array[end] >= tmp) {
                end--;
            }
            while (start < end && array[start] <= tmp) {
                start++;
            }
            swap(array,start,end);
        }
        swap(array,i,start);
        return start;
    }

    /**
     * 堆排
     * @param array
     */
    public static void HeapSort(int[] array){
        createHeap(array);
        int end = array.length-1;
        while (end >= 0) {
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    public static void createHeap(int[] array) {
        for (int parant = (array.length-1-1)/2; parant >= 0 ; parant--) {
            shiftDown(array,parant,array.length);
        }
    }
    public static void shiftDown(int[] array,int parent,int len) {
        int child = parent*2+1;
        while (child < len) {
            if(child+1 < len &&array[child] < array[child+1]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = parent*2+1;
            } else {
                break;
            }
        }
    }

    /**
     * 冒泡排序（每一趟把最大的往后放）
     * @param array
     */
    public static void bubleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]){
                    swap(array,j,j+1);
                }
            }
        }
    }

    /**
     * 归并排序
     * @param array
     */
    public static void MergeSort(int[] array) {
        mergesort(array,0,array.length-1);
    }
    public static void mergesort(int[] array,int strat,int end) {
        if(strat >= end) {
            return;
        }
        int mid = strat+((end-strat)>>>1);
        mergesort(array,strat,mid);
        mergesort(array,mid+1,end);
        mergehelp(array,strat,end,mid);
    }
    public static void mergehelp(int[] array,int start,int end,int mid) {  //二路归并
        int[] array1 = new int[end-start+1];
        int s1 = start;
        int s2 = mid+1;
        int e1 = mid;
        int e2 = end;
        for (int i = 0; i < array1.length; i++) {
            if(s1 > e1) {
                array1[i] = array[s2];
                s2++;
                continue;
            }
            if(s2 > e2) {
                array1[i] = array[s1];
                s1++;
                continue;
            }
            if(array[s1] > array[s2]) {
                array1[i] = array[s2];
                s2++;
            } else {
                array1[i] = array[s1];
                s1++;
            }
        }
        for (int i = 0; i < array1.length; i++) {
            array[i+start] = array1[i];
        }
    }

    /**
     *
     * @param arr
     * @return
     */
    public static void MySort (int[] arr) {
        // write code here
        int begin = 0;
        int end = arr.length-1;
        MergeSortHelp(arr,begin,end);
    }
    public static void MergeSortHelp(int[] array,int begin,int end) {
        if(begin >= end) return;
        int mid = begin+((end-begin)>>>1);
        MergeSortHelp(array,begin,mid);
        MergeSortHelp(array,mid+1,end);
        func(array,begin,end,mid);
    }
    public static void func(int[] array,int begin,int end ,int mid) {
        int s1 = begin;
        int s2 = mid+1;
        int e1 = mid;
        int e2 = end;
        int[] newarray = new int[end-begin+1];
        for(int i = 0;i <newarray.length;i++) {
            if(s1>e1) {
                newarray[i] = array[s2];
                s2++;
                continue;
            }
            if(s2>e2) {
                newarray[i] = array[s1];
                s1++;
                continue;
            }
            if(array[s1] > array[s2]) {
                newarray[i] = array[s2];
                s2++;
            }else {
                newarray[i] = array[s1];
                s1++;
            }
        }
        for(int i = 0;i<newarray.length;i++) {
            array[i+begin] = newarray[i];
        }
    }
    public static void test2(int a) {
        int[] array = new int[a];
        Random random = new Random();
        for (int i = 0; i < a; i++) {
            array[i] = random.nextInt(a);
        }
        long start = System.currentTimeMillis();
        //insertSort(array);
        //shellSort(array);
        //selectSort(array);
        //bubleSort(array);
        //MergeSort(array);
        //HeapSort(array);
        quickSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end-start);
    }

    public static void main3(String[] args) {
        test2(100_0000);
    }
    public static void main(String[] args) {
        int[] nums1 = {3,2,1,4};
        //insertSort(nums1);  //插入排序
        //shellSort(nums1);   //希尔排序
        //selectSort(nums1);  //选择排序
        //quickSort(nums1);   //快排
        //HeapSort(nums1);    //堆排
        //bubleSort(nums1);   //冒泡
        //MergeSort(nums1);
        HeapSort(nums1);
        ArrayList<Integer> arrayList = new ArrayList<>();
        System.out.println(Arrays.toString(nums1));
    }
}
